package interview.huawei.tjt.od;

/**
 * @Author CandyWall
 * @Date 2022/2/22--15:58
 * @Description
 */
public class P3_1 {
    public static void main(String[] args) {
        /*int[][] lis = {{2, 1, 1},
                       {1, 2, 1},
                       {3, 1}, 
                       {1, 1, 2}, 
                       {1, 1, 1, 1}};*/
        int[][] lis = {{2, 1, 1, 2},
                       {1, 2, 1, 1, 1},
                       {3, 1, 2},
                       {1, 1, 2, 2},
                       {1, 1, 1, 2, 1}};
        // 计算墙的宽度
        int width = 0;
        for (int i = 0; i < lis[0].length; i++) {
            width += lis[0][i];
        }
        // 计算每块砖的最右边到墙壁最左边的距离，也就是每块砖的缝隙
        for (int i = 0; i < lis.length; i++) {
            for (int j = 1; j < lis[i].length; j++) {
                lis[i][j] += lis[i][j - 1];
            }
        }
        /*for (int i = 0; i < lis.length; i++) {
            System.out.println(Arrays.toString(lis[i]));
        }*/

        // 假设一刀切下去所有行的砖都碎了，这个为最小值，经过下面的循环以后这个值会变小
        int minBreakBricks = lis.length;
        // 刀口为 1到width - 1
        for (int k = 1; k < width; k++) {
            int breakBricks = 0;
            for (int i = 0; i < lis.length; i++) {
                // 检查这一行有没有缝隙对应这个刀口
                boolean canBreak = true;
                for (int j = 0; j < lis[i].length; j++) {
                    // 有缝隙就不能打断
                    if (lis[i][j] == k) {
                        canBreak = false;
                        break;
                    }
                }
                if(canBreak) breakBricks++;
            }
            System.out.println(breakBricks);
            if (minBreakBricks > breakBricks) {
                minBreakBricks = breakBricks;
            }
        }
        System.out.println(minBreakBricks);
    }
}